#include <iostream>
#include <vector>
using namespace std;

const int MAX = 100;

struct Node {
	int power;
	Node* lchild,
		* rchild;
};

class HuffmanTree {
public:
	const int& PWL; //树的权值（只读）
	const vector<int>& powers; //权值数组（只读）

	HuffmanTree();
	~HuffmanTree();
	void Create(int a[]); //创建哈夫曼树
private:
	vector<Node*> _forest; //哈夫曼森林
	vector<int> _powers; //权值数组
	int _pwl; //树的权值

	void Release(Node* node); //递归销毁树
	void CountWeight(Node* node, int len); //递归计算权值
	void AddNode(Node* s);//将结点 s 加入到森林(链表)，并确保链表各结点的权值是从小到大排列
};

HuffmanTree::HuffmanTree() :PWL(_pwl), powers(_powers)
{
	_pwl = 0;
}

HuffmanTree::~HuffmanTree()
{
	if (_forest.size() > 0)
	{
		Release(_forest[0]);
	}
}

void HuffmanTree::Create(int a[]) {
	int i = 0;
	while (a[i] != 0)
	{
		_powers.push_back(a[i]);
		Node* s = new Node;
		s->power = a[i];
		s->lchild = s->rchild = NULL;
		AddNode(s);
		i++;
	}

	//创建树的过程
	while (_forest.size() > 1)
	{
		Node* p1, * p2, * p3;
		p1 = _forest.front(); //最小权值
		_forest.erase(_forest.begin());
		p2 = _forest.front(); //次小权值
		_forest.erase(_forest.begin());
		//组装新结点, p1 和 p2 分别为其左右子树
		p3 = new Node();
		p3->power = p1->power + p2->power;
		p3->lchild = p1;
		p3->rchild = p2;
		//将结点加入到森林(加入链接)
		AddNode(p3);
	}

	//从根结点开始编码
	if (_forest.size() > 0)
	{
		CountWeight(_forest[0], 0);
	}
}

void HuffmanTree::Release(Node* node)
{
	if (NULL == node)
	{
		return;
	}
	Release(node->lchild);
	Release(node->rchild);
	delete node;
}

void HuffmanTree::CountWeight(Node* node, int len)
{
	//叶结点累加权值
	if (node->lchild == NULL && node->rchild == NULL)
	{
		_pwl += node->power * len;
	}
	else {
		if (node->lchild)
		{
			CountWeight(node->lchild, len + 1);
		}
		if (node->rchild)
		{
			CountWeight(node->rchild, len + 1);
		}
	}
}

void HuffmanTree::AddNode(Node* s)
{
	vector<Node*>::iterator i = _forest.begin();
	while (i != _forest.end() && (*i)->power <= s->power)
	{
		i++;
	}
	//将新结点 s 放到 p 的后面
	_forest.insert(i, s);
}

int main()
{
	int n,
		i;

	cin >> n;
	int** a = new int* [n];
	if (!a)
	{
		cout << "内存申请错误！" << endl;
		return 1;
	}

	for (i = 0; i < n; i++)
	{
		a[i] = new int[MAX];
		if (!a[i])
		{
			cout << "内存申请错误！" << endl;
			return 1;
		}
		int j = -1;
		do
		{
			j++;
			cin >> a[i][j];
		} while (a[i][j]);
	}

	for (i = 0; i < n; i++)
	{
		HuffmanTree ht;
		ht.Create(a[i]);
		cout << ht.PWL << endl;
	}

	for (i = 0; i < n; i++)
	{
		delete[] a[i];
	}
	delete[] a;

	system("pause");
	return 0;
}
